1. Technical Field of the Invention
The present invention relates in general to the telecommunications field and, in particular, to echo cancellation in telephony systems.
2. Description of Related Art
"Echo" is a phenomenon that can occur in a telephony system whenever a portion of transmitted speech signal energy is reflected back to a sender. These reflections are caused by impedance mismatches in analog portions of the telephony network. There can be many different sources of echo, such as, for example, a hybrid circuit that converts a 4-wire line to a 2-wire line in a Public Switched Telephone Network (PSTN) subscriber interface, or acoustical cross-talk in a mobile radiotelephone. The presence of echo along with a substantial delay (e.g., physical distance or processing delay) can severely degrade the quality of the speech signals being processed.
An echo canceller is a device that is commonly used in telephony systems to suppress or remove echos in long distance traffic. For example, in cellular Public Land Mobile Networks (PLMNs), echo cancellers are used in mobile services switching centers (MSCs) to suppress or remove echos in speech traffic. Echo cancellers are also used in mobile radiotelephones and "handsfree" telephone equipment to compensate for acoustical echos. A general description of an existing echo cancellation technique can be found in the paper entitled: "A Double Talk Detector Based on Coherence" by Gansler et al, Signal Processing Group, Dept. of Elec. Eng. and Comp. Science, Lund University, Sweden.
FIG. 1 is a simplified schematic block diagram of a conventional echo canceller (10). The main component of such an echo canceller is an adaptive finite-impulse-response (FIR) filter 12. Under the control of an adaptation algorithm (e.g., executed in software), filter 12 models the impulse response of the echo path. Typically, filter 12 is adapted using a Least Mean Squares (LMS) algorithm. A non-linear processor (NLP) 14 is used to remove residual echo that may remain after linear processing of the input signal.
The signals involved in a telephone call are nonstationary in nature. Consequently, the echo canceller (10) typically includes a double-talk detector (DTD) 16, which is used to control and inhibit the adaptation process when the echo signal to "near end" signal ratio is of such a value that no additional improvement in the echo path estimation can be obtained by further adaptation of filter 12. However, in order to be able to track variations in the echo path, it is not possible to inhibit the adaptation too often, and under those conditions some degradation of the echo path estimate will occur if the echo signal-to-noise ratio worsens. The block denoted by 18 represents the echo source in the telephony system which generates the "desired" signal, y(t), as a function of the "far end" signal, x(t), and the "near end" signal, v(t).
A dual filter structure that has been proposed to cope with this degradation problem was described in the article entitled: "Echo Canceller with Two Echo Path Models," by Kazuo Ochiai et al, IEEE Transactions on Communications, Vol. COM-25, No. 6, June 1977. As shown generally in FIG. 2, the technique described in this article uses a fixed filter (20) for echo cancellation and an adaptive filter (22) for echo path estimation. If a good enough echo path estimate can be obtained by the adaptive filter (22), the coefficients of the adaptive filter are copied into the fixed filter (20). Consequently, these better coefficients can be used for the cancellation if the echo path estimate worsens.
An improvement to the control strategy for the dual filter structure described directly above has been disclosed in a commonly-assigned Swedish Patent No. 9503640-6, entitled "An Adaptive Dual Filter Echo Cancellation Method" to Johnny Karlsen et al. According to the method described therein, both filters are used for echo cancellation, and the filters' coefficients can be transferred in both directions. This patent describes certain conditions used to decide which of the two filter outputs, e.sub.a or e.sub.f, are to be used as the output for the echo canceller, as well as when the coefficients are to be transferred from one filter to the other. These decisions are based on comparisons of power and correlation estimates for the signals involved, and, therefore, make the algorithms being used highly data dependent.
Most existing echo cancellers utilize a general purpose digital signal processor (DSP) as a central computational element. A generic, general purpose DSP architecture that has been used for echo cancellation is shown in FIG. 3. For example, referring to FIG. 3, a DSP 30 used for echo cancellation includes two data memory sections 32 and 34 and corresponding data busses 32a and 34a, an address arithmetic unit (AAU) 36, a multiplier section 38, an arithmetic logic unit (ALU) 40, and a shifter 42.
Also, it has been possible to assemble an echo canceller from computational blocks that correspond to the functional blocks in the adaptive algorithm described above in the Ochiai et al article (FIG. 2). However, since the filter adaptation technique described therein relies on use of the current error signal, e(t), which is available for the first time only after the filtering process has been performed, the operations that correspond to the functional blocks in the Ochiai algorithm would have to be executed in series anyway, and no significant efficiencies would be derived. Moreover, the substantial amount of hardware needed to accomplish such functions would not significantly improve the overall performance of an echo canceller.
A problem arises if "long" filters (e.g., N=512 or more) are utilized for adaptive echo cancellation, since a relatively large number of computations have to be performed. In that case, it is very important to optimize the processor's architecture to match the functions of the algorithm being used. At the same time, it is also important to keep the amount of hardware resources being used within reasonable limits.
A general purpose DSP used for echo cancellation (e.g., DSP 30 in FIG. 3) has only two data busses (e.g., 32a, 34a). Consequently, such a DSP is only capable of making a maximum of two memory accesses per clock cycle (e.g., one access to each of the memory sections 32 and 34). Consequently, there was a data transfer bottleneck that significantly lowered the DSP's computational efficiency.
For example, the LMS update equation for an algorithm executed by such a DSP can be expressed as: EQU h.sub.n (t+1)=h.sub.n (t)+.alpha.(t)x.sub.n (t), (1)
where .alpha.(t)=.mu.e(t) if a basic LMS value is used, or ##EQU1## if a normalized LMS value is used. In any event, .alpha.(t) is a constant multiplier during each sample interval. In Equation 1 above, x.sub.n (t) is the nth signal sample at time t, h.sub.n (t) is the nth adaptive filter coefficient at time t, e(t) is the error signal, and .mu. is a small constant that represents the sample stepsize.
In most signal processors, the multiplier, a(t), can be stored in a multiplier register and maintained there until all of the filter coefficients have been updated. Then, the LMS update equation (Equation 1) requires two read operations from the memory sections and one write operation to the coefficient memory section. These operations cannot be accomplished over the two data busses during a single clock cycle, and consequently, two clock cycles are required to run an update for each value of N. Generally, N is determined by the length of the impulse response of the echo path involved. A value of 512 for N is quite commonly used for typical echo cancellation applications. However, N can be as high as several thousand for acoustical echo cancellation applications.
The process of filtering the input signal with a FIR filter can be expressed as follows: ##EQU2## which obviously requires one clock cycle per value of N to compute an output sample, y(t). Since the dual filter technique described earlier utilizes two FIR filters, it follows that two clock cycles per value of N would be needed to compute the corresponding two output samples.
Coefficients of the two FIR filters are copied from one to the other according to decisions made by a signal dependent control algorithm. If it is desirable to perform FIR filtering with a single clock cycle per value of N, as assumed above, then the coefficients for both filters should be located in one memory section, and the signal samples, x(t), should be located in the other memory section. This arrangement implies that the coefficient copy operation would require two cycles per value of N, because copying one filter coefficient would require two accesses to the same memory section.
Consequently, the peak complexity of the complete filtering portion of the dual filter approach described above is measured as 6*N for a general purpose DSP. In other words, the general purpose DSP would take 6*N cycles to complete the filter computations. However, this level of complexity is relatively high for the large values of N that are required in echo canceller applications, which leaves only a relatively small (if any) processing capacity for the control portion of the algorithm and other necessary echo canceller functions.